home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_02 / 9n02031b < prev    next >
Text File  |  1990-12-26  |  3KB  |  86 lines
  1.  
  2.  
  3. /* Quick sort routine (not recursive) */
  4.  
  5. /* Prototypes */
  6. void QuickSort( int *List, int Begin, int End );
  7. void ShellSort( int *List, int Begin, int End );
  8.  
  9. #define MAXSTACK 200
  10. int Stack[MAXSTACK];
  11. int StackPoint;
  12.  
  13. void
  14. QuickSort( int *List, int Begin, int End )
  15. {
  16.         int Value, Tmp, i, j;
  17.  
  18.         StackPoint = 2;
  19.         do
  20.         {
  21.                 /* Divide the list in two */
  22.                 Value = List[End];
  23.                 i = Begin - 1;
  24.                 j = End;
  25.                 do {
  26.                         while( List[++i] < Value );
  27.                         while( List[--j] > Value );
  28.                         Tmp = List[i];
  29.                         List[i] = List[j];
  30.                         List[j] = Tmp;
  31.                 } while( j > i );
  32.                 List[j] = List[i];
  33.                 List[i] = List[End];
  34.                 List[End] = Tmp;
  35.                 /* If more than 2 items push the first part */
  36.                 if( i - Begin > 2 )
  37.                 {
  38.                         if( StackPoint >= MAXSTACK )
  39.                                 ShellSort( List, Begin, i-1 );
  40.                         else
  41.                         {
  42.                                 Stack[StackPoint++] = i-1;
  43.                                 Stack[StackPoint++] = Begin;
  44.                         }
  45.                 }
  46.                 if( End - i > 2)
  47.                 {
  48.                         if( StackPoint >= MAXSTACK )
  49.                                 ShellSort( List, i+1, End );
  50.                         else
  51.                         {
  52.                                 Stack[StackPoint++] = End;
  53.                                 Stack[StackPoint++] = i+1;
  54.                         }
  55.                 }
  56.                 Begin = Stack[--StackPoint];
  57.                 End = Stack[--StackPoint];
  58.         } while( StackPoint );
  59. }
  60.  
  61. /* Shell sort for when the stack is full */
  62. void
  63. ShellSort( int *List, int Begin, int End )
  64. {
  65.         int i, j, Mid, Value;
  66.  
  67.         for( Mid = 1; Mid <= End - Begin + 1; )
  68.                 Mid = 3 * Mid + 1;
  69.         do {
  70.                 Mid /= 3;
  71.                 for( i=Mid+1; i <= End - Begin + 1; i++ )
  72.                 {
  73.                         Value = List[Begin+i];
  74.                         j = i;
  75.                         while( j > Mid
  76.                                 && List[Begin+j-Mid] > Value )
  77.                                 {
  78.                                 List[Begin+j] = List[Begin+j-Mid];
  79.                                 j = j - Mid;
  80.                                 }
  81.                         List[Begin+j] = Value;
  82.                         }
  83.         } while( Mid != 1 );
  84.  
  85. }
  86.